package leetcode.list;

/**
 * @author : zx
 * @version V1.0
 */
public class reverseList {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode next = head.next;
        head.next = null;
        ListNode old = null;
        while(next != null){
            old = head;
            head = next;
            next = next.next;
            head.next = old;
        }
        return head;
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode next = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return next;
        }
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode next = head;
        ListNode old = head;
        for(int i = 1; i < m; i++){
            old = next;
            next = next.next;
        }


        ListNode head1 = next; // 2
        ListNode next0 = old; // 1
        ListNode next1 = next; // 2
        ListNode next2 = next.next; // 3


        for(int i = m; i < n; i++){
            next1.next = next0;
            next0 = next1; // 2
            next1 = next2; // 3
            next2 = next2.next; // 4
        }
        next1.next = next0;

        old.next = next1;
        head1.next = next2;
        if (m == 1){
            return next1;
        }
        return head;


    }

    public static class ListNode {
    int val;
     ListNode next;
   ListNode(int x) { val = x; }
 }

    public static void main(String[] args){
        ListNode a1 = new ListNode(1);
        ListNode a2 = new ListNode(2);
        ListNode a3 = new ListNode(3);
        ListNode a4 = new ListNode(4);
        ListNode a5 = new ListNode(5);
        a1.next =a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        reverseBetween(a1, 1,5);

    }
}
